/*
 * heuristicGenerator.h
 *
 *  Generates the heuristic tables for the A* algorithm CF
 *
 *  Created on: Oct 1, 2013
 * @author Daniel Rogers
 */

#ifndef HEURISTICGENERATOR_H_
#define HEURISTICGENERATOR_H_

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <stdbool.h>

#include "cube.h"
#include "utils.h"
#include "cubeQueue.h"

//Used for table keys
#define KEYS_PER_SET 4
typedef struct
{
    //This stores 4 keys in 13 bytes
    //  keys need 26 bits -> 8 * 13 / 16 = 4
    //4 32 bit keys would need 16 bytes
    //  This is a savings of ~18%
    uint8_t keys[13];
} EdgekeySet;

/*
 * Generates the heuristic tables and places them in the default table files
 *
 * @return true if the generation was successful
 */
bool generateTables();

/*
 * Generates all the unique corner states
 * @param htables The heuristic tables to populate.
 *                This will populate htables[0]
 * @param queue A queue containing the initial state to use for expansion
 */
void generateCorners(uint8_t * htables[3], Queue * queue);

/*
 * Generates all the unique edge states for both sets
 * @param htables The heuristic tables to populate.
 *                This will populate htables[1] and htables[2]
 * @param queue A queue containing the initial state to use for expansion
 */
void generateEdges(uint8_t * htables[3], Queue * queue);

/*
 * Recursively expand all nodes to a depth of limit
 */
void recurseExpand(uint8_t * htables[3], Cube * current,
        const Cube * const prev, const Cube * const prev2, uint8_t depth,
        uint8_t limit);

/*
 * Stores a distance value to a state inside a heuristic table
 *
 * @param htable A pointer to the table to store in
 * @param index The location to store it in
 * @param dist The distance to store at that location
 *
 */
void storeHeuristic(uint8_t * htable, const uint32_t index, uint8_t dist);

/*
 * Looks up in the map of edgekeys to see if a key exists.
 * If the key is not found, it will be added to the table
 *
 * @param table The table to look in
 * @param lens The number of items in each table cell
 * @param index The index in the table to look at
 * @param key The key to look for
 *
 * @return true if the key is found
 */
bool edgeTableContains(EdgekeySet ** table, uint16_t * lens, uint32_t index,
        uint32_t key);

/*
 * Extracts a key from a keyset
 *
 * @param set The keyset to extract from
 * @param loc The position inside the keyset to extract
 *
 * @return The extracted key
 */
uint32_t extractKey(EdgekeySet * set, uint8_t loc);

/*
 * Inserts a key into a keyset
 *
 * @param set The keyset to insert into
 * @param key The key to insert
 * @param loc The position inside the keyset to insert
 *
 */
void insertKey(EdgekeySet * set, uint32_t key, uint8_t loc);

/*
 * Initializes the edge table
 * Expects table and lens to already be malloced to CUBE_EDGE_BUCKETS size
 */
void initEdgeTable(EdgekeySet ** table, uint16_t * lens);

/*
 * Frees everything in the edge table and frees lens
 */
void freeEdgeTable(EdgekeySet ** table, uint16_t * lens);

#endif /* HEURISTICGENERATOR_H_ */
